# 第9章 递归
# 概念
递归是一种解决问题的方法，他从解决问题的各个小部分开始，直到解决最初的大问题。递归通常涉及函数调用自身。
# 计算阶乘
function factorialIterative(number) {
if (number < 0) {
return undefined
}
let total = 1
for (let n = number; n > 1; n--) {
total *= n
}
return total
}
function factorial(n) {
if (n < 0) {
return undefined
}
if (n === 1 || n === 0) {
return 1
}
return n * factorial(n - 1)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 斐波那契数列
//斐波那契数列
function fibonacci(n) {
if (n < 1) {
return 0
}
if (n <= 2) {
return 1
}
return fibonacci(n - 1) + fibonacci(n - 2)
}
//迭代
function fibonacciIterative(n) {
if (n < 1) {
return 0
}
let fibNMinus2 = 0
let fibNMinus1 = 1
let fibN = n
for (let i = 2; i <= n; i++) {
fibN = fibNMinus1 + fibNMinus2
fibNMinus2 = fibNMinus1
fibNMinus1 = fibN
}
return fibN
}
//记忆化斐波那契数列
//记忆化是一种保存前一个结果的值的优化技术，类似于缓存。
function fibonacciMemoization(n) {
if (n < 1) {
return 0
}
const memo = [0, 1]
const fibonacciMem = num => {
if (memo[num] != null) {
return memo[num]
}
return (memo[num] = fibonacciMem(num - 1) + fibonacciMem(num - 2))
}
return fibonacciMem(n)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 尾调用优化
es6 中有尾调用优化（tail call），如果函数内的最后一个操作是调用函数，会通过‘跳转指令’而不是‘子程序调用’来控制。也就是说，在 es6 中代码会一直执行下去。因此，具有停止递归的基线条件非常重要。
function Fibonacci(n, ac1 = 1, ac2 = 1) {
if (n <= 1) {
return ac2
}
return Fibonacci(n - 1, ac2, ac1 + ac2)
}
1
2
3
4
5
6
7
2
3
4
5
6
7
迭代版本比递归的版本要快的多，所以这表示递归更慢。但是递归版本更容易理解，需要的代码通常也更少。另外，对一些算法来说，迭代的解法可能不可用，而且有了尾调用优化，递归的多余消耗甚至可能被消除。